package Tree;

import java.util.ArrayList;
import java.util.List;

public class _103_BinaryTreeZigzagLevelOrderTraversal {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if(root==null) return res;
        List<TreeNode> nodes = new ArrayList<>();
        boolean reverse = false;
        nodes.add(root);
        while (!nodes.isEmpty()) {
            List<TreeNode> tmp = new ArrayList<>();
            List<Integer> tres = new ArrayList<>();
            for (TreeNode node : nodes) {
                if (node.left != null) {
                    tmp.add(node.left);
                }
                if (node.right != null) {
                    tmp.add(node.right);
                }
            }
            if (reverse) {
                for (int i = nodes.size() - 1; i >= 0; i--) {
                    tres.add(nodes.get(i).val);
                }
                reverse = false;
            } else {
                for (int i = 0; i < nodes.size(); i++) {
                    tres.add(nodes.get(i).val);
                }
                reverse = true;
            }
            nodes = tmp;
            res.add(tres);
        }
        return res;
    }

}
